Parametric signal processing is used in many areas, such as speech and image analysis, synthesis and recognition, neurophysics, geophysics, array processing, computerized tomography, communications and astronomy, to name but a few.
One example of signal processing of particular importance is the linear prediction technique, which is used for speech analysis, synthesis and recognition, and for the processing of seismic signals, to enable the reconstruction of geophysical substrata. The linear prediction technique employs a specialized autocorrelation function.
Another form of signal processing which finds a multitude of applications, is the determination of an optimal (in the least square sense) finite impulse response filter. A signal processor employing such a technique works with the autocorrelation of the filter input signal and the cross-correlation between the input and the desired response signal, and may be used in many of the above-mentioned applications.
Still another form of signal processing of particular importance is known in the art as "L-step ahead" prediction and filtering, for solving the "optimum lag" problem. This technique is especially useful in designing spiking and shaping filters. Signal processors which perform this function employ a specialized autocorrelation function which also takes into account a time lag associated with the system.
Generally, as the order of the system under investigation increases, the complexity of the signal processing necessary to provide useful information also increases. For example, using the general Gaussian elimination procedure, a system of order p can be processed in "O(p.sup.3)" steps, indicating the number of steps as being "on the order of" p.sup.3, i.e., a function of p cubed. Thus, it will be appreciated that a system having order of p=100 requires on the order of one million processing steps to process the signal, a limitation of readily apparent significance, especially where real time processing is required.
Signal processing techniques have been developed which have reduced the number of operations required to process a signal. One such method has been based on a technique developed by N. Levinson, which requires O(p.sup.2) sequential operations to process the signal. In particular, the "Levinson technique" requires O(2.multidot.p.sup.2) sequential operations in order to process the signal. An improved version of this technique, known as the "Levinson-Durbin" technique requires O(1.multidot.p.sup.2) sequential operations to process the signal. Neither of these schemes is suitable for parallel implementation. On the general subject of the Levinson and Levinson-Durbin techniques, see N. Levinson, "The Wiener RMS (Root-Mean-Square) Error Criterion in Filter Design and Prediction", J. Math Phys., Vol. 25, pages 261-278, January 1947; and J. Durbin, "The Fitting of Time Series Models", Rev. Int. Statist. Inst., Vol. 28, pages 233-244, 1960.
Although they represent an order of magnitude improvement over the Gaussian elimination technique, the Levinson and Levinson-Durbin techniques are too slow for many complex systems where real time processing is required.
Another way of implementing the main recursion of the Levinson-Durbin technique, for the computation of what is widely known as "lattice coefficients", was developed by Schur in 1917, in order to establish a system stability criterion. See I. Schur, "Uber Potenzreihen Die Im Innern Des Einheitskreises Beschrankt Sind", J. Reine Angewandte Mathematik, Vol. 147, 1917, pages 205-232. Lev-Ari and Kailath, of Stanford University, have developed a different approach, based on the Schur and Levinson techniques, which provides a triangular "ladder" structure for signal processing. The Lev-Ari and Kailath technique uses the signal, per se, as the input to the processor, rather than autocorrelation coefficients, and it is used in the signal modelling context. See H. Lev-Ari and T. Kailath, "Schur and Levinson Algorithms for Nonstationary Processes", IEEE International Conference on Acoustics, Speech and Signal Processing, 1981, pages 860-864.
In another modification to the Schur technique, Le Roux and C. Gueguen re-derived the Schur algorithm, giving emphasis to the finite word length implementation, using fixed point arithmetics. See Le Roux and Gueguen, "A Fixed Point Computation of Partial Correlation, Coefficients", IEEE Transactions on Acoustics, Speech, and Signal Processing, June 1977, pages 257-259.
Finally, Kung and Hu, have developed a parallel scheme, based on the Schur technique, which uses a plurality of parallel processors, to process a signal, having order p, in O(p) operations, a significant improvement compared to the Levinson-Durbin technique. See Kung and Hu, "A Highly Concurrent Algorithm and Pipelined Architecture for Solving Toeplitz Systems", IEEE Transactions on Acoustics, Speech and Signal Processing, Vol. ASSP-31, No. 1, February 1983, pp. 66-76. However, the application of the Kung and Hu technique is severely limited insofar as it requires that the number of processors be equal to the order of the system to be solved. Thus, the Kung and Hu technique cannot process a signal produced by a system having an order greater than the number of parallel processors. System complexity is therefore a major limiting factor in using the Kung and Hu technique, insofar as many complex systems may have orders much higher than the number of parallel processors currently available in modern VLSI or other technology.